package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.*;

public class _90_subset {
    
    /**
     * 不得不出此下策，不知道怎么去重？
     * */
    static class bad {
        Set<List<Integer>> res = new HashSet<>();
        List<Integer> each = new ArrayList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            back(nums, 0);
            return new ArrayList<>(res);
        }
    
        void back(int[] nums, int i) {
            if (i == nums.length) res.add(new ArrayList<>(each));
            else {
                each.add(nums[i]);
                back(nums, i + 1);
                each.remove(each.size() - 1);
                back(nums, i + 1);
            }
        }
    }
    
    /**
     * 如果俩数相等，只能都选或都不选？
     * 肯定不是这个意思， 1 2 2，只能 1 或  1 2 2 不能 1 2？肯定不是。
     * 这个比较难想，前一个没选，自己也不能选；因为选自己，包含在了选前一个的情况里，前一个选了就行了
     * */
    static class ok {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            back(false, nums, 0);
            return res;
        }
        
        void back(boolean prevChosen, int[] nums, int i) {
            if (i == nums.length) res.add(new ArrayList<>(each));
            else {
                back(false, nums, i + 1);
                if (!prevChosen && i > 0 && nums[i] == nums[i - 1]) return;
                each.add(nums[i]);
                back(true, nums, i + 1);
                each.remove(each.size() - 1);
            }
        }
    }
    
    static class bitwise {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            int n = nums.length;
            for (int mask = 0, limit = 1 << n; mask < limit; mask++) {
                each.clear();
                boolean flag = true;
                for (int j = 0; j < n; j++) {
                    if ((mask & 1 << j) != 0) {
                        if (j > 0 && nums[j - 1] == nums[j] && (mask & 1 << (j - 1)) == 0) {
                            flag = false;
                            break;
                        }
                        each.add(nums[j]);
                    }
                }
                if (flag) {
                    res.add(new ArrayList<>(each));
                }
            }
            return res;
        }
    }
    
}
